SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Memory-hard function</title>

</head>

Memory-hard function

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">In <a href="Cryptography" title="Cryptography">cryptography</a>, a memory-hard function (MHF) is a function that costs a significant amount of <a href="Random-access_memory" title="Random-access memory">memory</a> to efficiently evaluate.<a href="#cite_note-:0-1">[1]</a> It differs from a <a href="Memory-bound_function" title="Memory-bound function">memory-bound function</a>, which incurs cost by slowing down computation through memory latency.<a href="#cite_note-2">[2]</a> MHFs have found use in <a href="Key_stretching" title="Key stretching">key stretching</a> and <a href="Proof_of_work" title="Proof of work">proof of work</a> as their increased memory requirements significantly reduce the computational efficiency advantage of custom hardware over general-purpose hardware compared to non-MHFs.<a href="#cite_note-:1-3">[3]</a><a href="#cite_note-:0-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Introduction">Introduction</h2></div>

MHFs are designed to consume large amounts of memory on a computer in order to reduce the effectiveness of <a href="Parallel_computing" title="Parallel computing">parallel computing</a>. In order to evaluate the function using less memory, a significant time penalty is incurred. As each MHF computation requires a large amount of memory, the number of function computations that can occur simultaneously is limited by the amount of available memory. This reduces the efficiency of specialised hardware, such as <a href="Application-specific_integrated_circuit" title="Application-specific integrated circuit">application-specific integrated circuits</a> and <a href="Graphics_processing_unit" title="Graphics processing unit">graphics processing units</a>, which utilise parallelisation, in computing a MHF for a large number of inputs, such as when <a href="Brute-force_attack" title="Brute-force attack">brute-forcing</a> password hashes or <a href="Cryptocurrency" title="Cryptocurrency">mining cryptocurrency</a>.<a href="#cite_note-:0-1">[1]</a><a href="#cite_note-:2-4">[4]</a>

<div class="mw-heading mw-heading2"><h2 id="Motivation_and_examples">Motivation and examples</h2></div>

<a href="Bitcoin" title="Bitcoin">Bitcoin</a>'s proof-of-work uses repeated evaluation of the <a href="SHA-2" title="SHA-2">SHA-256</a> function, but modern general-purpose processors, such as off-the-shelf <a href="Central_processing_unit" title="Central processing unit">CPUs</a>, are inefficient when computing a fixed function many times over. Specialized hardware, such as application-specific integrated circuits (ASICs) designed for Bitcoin mining, can use 30,000 times less energy per hash than <a href="X86" title="X86">x86</a> CPUs whilst having much greater hash rates.<a href="#cite_note-:2-4">[4]</a> This led to concerns about the centralization of mining for Bitcoin and other cryptocurrencies.<a href="#cite_note-:2-4">[4]</a> Because of this inequality between miners using ASICs and miners using CPUs or off-the shelf hardware, designers of later proof-of-work systems utilised hash functions for which it was difficult to construct ASICs that could evaluate the hash function significantly faster than a CPU.<a href="#cite_note-:1-3">[3]</a>

As memory cost is platform-independent,<a href="#cite_note-:0-1">[1]</a> MHFs have found use in cryptocurrency mining, such as for <a href="Litecoin" title="Litecoin">Litecoin</a>, which uses <a href="Scrypt" title="Scrypt">scrypt</a> as its hash function.<a href="#cite_note-:1-3">[3]</a> They are also useful in password hashing because they significantly increase the cost of trying many possible passwords against a leaked database of hashed passwords without significantly increasing the computation time for legitimate users.<a href="#cite_note-:0-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Measuring_memory_hardness">Measuring memory hardness</h2></div>

There are various ways to measure the memory hardness of a function. One commonly seen measure is cumulative memory complexity (CMC). In a parallel model, CMC is the sum of the memory required to compute a function over every time step of the computation.<a href="#cite_note-5">[5]</a><a href="#cite_note-6">[6]</a>

Other viable measures include integrating memory usage against time and measuring memory <a href="Bandwidth_(computing)" title="Bandwidth (computing)">bandwidth</a> consumption on a memory bus. Functions requiring high memory bandwidth are sometimes referred to as "bandwidth-hard functions".<a href="#cite_note-7">[7]</a>

<div class="mw-heading mw-heading2"><h2 id="Variants">Variants</h2></div>

MHFs can be categorized into two different groups based on their evaluation patterns: data-dependent memory-hard functions (dMHF) and data-independent memory-hard functions (iMHF). As opposed to iMHFs, the memory access pattern of a dMHF depends on the function input, such as the password provided to a key derivation function.<a href="#cite_note-8">[8]</a> Examples of dMHFs are <a href="Scrypt" title="Scrypt">scrypt</a> and <a href="Argon2" title="Argon2">Argon2d</a>, while examples of iMHFs are <a href="Argon2" title="Argon2">Argon2i</a> and <a href="Catena_(cryptography)" class="mw-redirect" title="Catena (cryptography)">catena</a>. Many of these MHFs have been designed to be used as <a href="Key_derivation_function" title="Key derivation function">password hashing functions</a> because of their memory hardness.

A notable problem with dMHFs is that they are prone to <a href="Side-channel_attack" title="Side-channel attack">side-channel attacks</a> such as cache timing. This has resulted in a preference for using iMHFs when hashing passwords. However, iMHFs have been mathematically proven to have weaker memory hardness properties than dMHFs.<a href="#cite_note-9">[9]</a>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFChen2019" class="citation thesis cs1">Chen, Binyi (2019). <a rel="nofollow" class="external text" href="https://escholarship.org/uc/item/7x4630qv">Memory-Hard Functions: When Theory Meets Practice</a> (Thesis). UC Santa Barbara.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFDworkGoldbergNaor2003" class="citation book cs1">Dwork, Cynthia; Goldberg, Andrew; Naor, Moni (2003). "On Memory-Bound Functions for Fighting Spam". In Boneh, Dan (ed.). Advances in Cryptology - CRYPTO 2003. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. pp. 426–444. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-45146-4_25">10.1007/978-3-540-45146-4_25</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-45146-4</bdi>.</cite>

</li>

<li id="cite_note-:1-3">^ <a href="#cite_ref-:1_3-0">a</a> <a href="#cite_ref-:1_3-1">b</a> <a href="#cite_ref-:1_3-2">c</a> <cite id="CITEREFLIU2013" class="citation web cs1">LIU, ALEC (2013-11-29). <a rel="nofollow" class="external text" href="https://www.vice.com/en/article/beyond-bitcoin-a-guide-to-the-most-promising-cryptocurrencies/">"Beyond Bitcoin: A Guide to the Most Promising Cryptocurrencies"</a>. Vice. Retrieved 2023-09-30.</cite>

</li>

<li id="cite_note-:2-4">^ <a href="#cite_ref-:2_4-0">a</a> <a href="#cite_ref-:2_4-1">b</a> <a href="#cite_ref-:2_4-2">c</a> <cite id="CITEREFBiryukovKhovratovich2015" class="citation book cs1">Biryukov, Alex; Khovratovich, Dmitry (2015). "Tradeoff Cryptanalysis of Memory-Hard Functions". In Iwata, Tetsu; Cheon, Jung Hee (eds.). Advances in Cryptology – ASIACRYPT 2015. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. pp. 633–657. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-662-48800-3_26">10.1007/978-3-662-48800-3_26</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-662-48800-3</bdi>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> (AS15) Alwen, Serbineko, <a rel="nofollow" class="external text" href="https://eprint.iacr.org/2014/238.pdf">High Parallel Complexity Graphs and Memory-Hard Functions</a>, 2015

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFAlwenBlockiPietrzak2017" class="citation arxiv cs1">Alwen, Joel; Blocki, Jeremiah; Pietrzak, Krzysztof (2017-07-07). "Sustained Space Complexity". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1705.05313">1705.05313</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.CR">cs.CR</a>].</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFBlockiLiuRenZhou2022" class="citation web cs1">Blocki, Jeremiah; Liu, Peiyuan; Ren, Ling; Zhou, Samson (2022). <a rel="nofollow" class="external text" href="https://eprint.iacr.org/2018/221.pdf">"Bandwidth-Hard Functions: Reductions and Lower Bounds"</a> (PDF). <a href="Cryptology_ePrint_Archive" title="Cryptology ePrint Archive">Cryptology ePrint Archive</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230112040047/https://eprint.iacr.org/2018/221.pdf">Archived</a> (PDF) from the original on 2023-01-12. Retrieved 2023-01-11.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFBlockiHarshaKangLee2019" class="citation book cs1">Blocki, Jeremiah; Harsha, Ben; Kang, Siteng; Lee, Seunghoon; Xing, Lu; Zhou, Samson (2019). <a rel="nofollow" class="external text" href="https://link.springer.com/chapter/10.1007/978-3-030-26951-7_20">"Data-Independent Memory Hard Functions: New Attacks and Stronger Constructions"</a>. In Boldyreva, Alexandra; Micciancio, Daniele (eds.). Advances in Cryptology – CRYPTO 2019. Lecture Notes in Computer Science. Cham: Springer International Publishing. pp. 573–607. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-030-26951-7_20">10.1007/978-3-030-26951-7_20</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-030-26951-7</bdi>.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> Alwen, J., Blocki, J. (2016). <a rel="nofollow" class="external text" href="https://doi.org/10.1007/978-3-662-53008-5_9">Efficiently Computing Data-Independent Memory-Hard Functions.</a>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-12" href="https://en.wikipedia.org/wiki/?title=Memory-hard_function&oldid=1290098532">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>